#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;



//int t,n,a[100010];
//int l[100010], r[100010], ans;
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> t;
//	while (t--) {
//		cin >> n;
//		ans = r[n + 1] = -1e9;
//		for (int i = 1; i <= n; i++) cin >> a[i];
//		for (int i = 1; i <= n; i++) l[i] = max(l[i - 1] - 1, a[i]+i);
//		for (int i = n; i; i--) r[i] = max(r[i + 1] - 1, a[i]-i);
//		for (int i = 2; i < n; i++)
//		{
//			ans = max(ans, l[i - 1] + a[i] + r[i + 1]);
//		}
//		cout << ans << '\n';
//	}
//
//	return 0;
//}

//pair<ll, ll> calc(int n, ll m) {
//	if (!n)return { 0, 0 };
//	ll len = 1ll << (n - 1), cnt = 1ll << (2 * n - 2);
//	pair<ll, ll> pos = calc(n - 1, m % cnt);
//	ll x = pos.first, y = pos.second;
//	if (m % cnt == 0) return { y,x };
//	if (m % cnt == 1)return { x,y + len };
//	if (m % cnt == 2)return { x + len,y + len };
//	if (m % cnt == 3)return { 2 * len - 1 - y,len - 1 - x };
//}
//
//int main() {
//	ll ans, n, s, d;
//	ans=abs(calc(n,s).second-calc(n,d).second);
//	cout << ans;
//	return 0;
//}